In the recent field of information processing technology, especially in the field of image compression/image recognition, the associative memory with a minimum distance retrieval function has been focused. The associative memory is very effective for the pattern matching performed to recognize the object, which is required for the intellectual information processing, and for the data compression utilizing data group so-called codebook. The associative memory is one of typical function memories for searching data with the highest similarity (short distance) to the input data sequence (retrieval data) among plural reference data stored in the associative memory. The use of the excellent retrieval function is expected to markedly improve the performance of the application with the pattern matching function such as the image compression and image recognition as described above.
Searching the data with the highest similarity to the input data from R reference data with W bit width is the basic process for the pattern matching (refer to Non-Patent Document 1). The minimum distance retrieval associative memory (refer to Patent Document 1) may be regarded as the core technology in the information processing such as the image compression and the image recognition. The fully parallel type minimum distance retrieval associative memories each with the retrieval function with respect to Hamming distance, Manhattan distance, and Euclidean distance as the simple distance have been already proposed. Each of the aforementioned distances may be expressed by the following formulae 1 and 2 (refer to Non-Patent Document 2).
                    D        =                              ∑                          i              =              1                        w                    ⁢                                          ⁢                                                                S                i                            -                              R                i                                                                                    [                  Formula          ⁢                                          ⁢          1                ]            . . . Hamming distance, Manhattan distance
                    D        =                                            ∑                              i                =                1                            w                        ⁢                                                  ⁢                                          (                                                      S                    i                                    -                                      R                    i                                                  )                            2                                                          [                  Formula          ⁢                                          ⁢          2                ]            . . . Euclidean distance
The term S={S1, S2, . . . , Sw} denotes the input data, and the term R={R1, R2, . . . , Rw} denotes the reference data. Assuming that each of Si and Ri takes 1-bit binary number, D becomes the Hamming distance in the formula 1. Assuming that each of Si and Ri takes n-bit (n>1) binary number, D becomes the Manhattan distance in the formula 1. Referring to the formula 2, the D becomes Euclidean distance.
Such art as fully parallel type minimum Hamming distance retrieval architecture [refer to Non-Patent Document 2] and fully parallel type minimum Manhattan distance retrieval architecture [Non-Patent Documents 3 and Patent Document 2] have been disclosed so far. The general structure of the fully parallel type associative memory which employs the aforementioned architecture is shown in FIG. 1.
The associative memory includes a unit data storage circuit (Unit Storage: US), a unit data comparator circuit (Unit Comparator: UC), a word comparator circuit (Word Comparator: WC), a Winner Line-up amplifier (Winner Line-up Amplifier: WLA) circuit 100, and a Winner Take All (WTA) circuit 200.
The unit data storage circuit stores the reference data. The unit data comparator circuit compares the reference data with the retrieval data. The word comparator circuit converts a comparison signal into a current value. The Winner Line-up amplifier circuit (WLA circuit: Winner Line-up Amplifier circuit) 100 converts a comparison current signal into a voltage to amplify. The Winner Take All circuit 200 further amplifies the output from the WLA circuit 100. The associative memory includes peripheral circuits such as a retrieval data storage circuit, a row decoder, a column decoder, and a Read/Write circuit.
The unit data comparator circuit UC compares the reference data with the retrieval data, and the word comparator circuit WC outputs a comparison current signal C indicating results of the comparison between the reference data and the retrieval data to the WLA circuit 100. The WLA circuit 100 converts the comparison current signal C into a comparison voltage signal LA and amplifies the comparison voltage signal LA. The WTA circuit 200 further amplifies the comparison voltage signal LA, and sets a threshold value to output 1 indicating the data with the highest similarity (Winner), and output 0 indicating the other data (Loser).
[Patent Document 1] Japanese Unexamined Patent Application Publication No. 2002-288985
[Patent Document 2] Japanese Unexamined Patent Application Publication No. 2005-209317
[Patent Document 3] Japanese Unexamined Patent Application Publication No. 2004-5825
[Non-Patent Document 1] D. R. Tveter, “The Pattern Recognition Basis of Artificial Intelligence,” Los Alamitos, Calif.: IEEE computer society, 1998.
[Non-Patent Document 2] H. J. Mattausch, T. Gyohten, Y. Soda, and T. Koide, “Compact Associative-Memory Architecture with Fully-Parallel Search Capability for the Minimum Hamming Distance,” IEEE Journal of Solid-State Circuits, Vol. 37, pp. 218-227, 2002.
[Non-Patent Document 3] H. J. Mattausch, N. Omori, S. Fukae, T. Koide and T. Gyohten, “Fully-Parrallel Pattern-Matching Engine with Dynamic Adaptability to Hamming or Manhattan Distance,” 2002 Symposium on VLSI Circuits Digest of Technical Papers, pp. 252-255, 2002.
[Non-Patent Document 4] Y. Yano, T. Koide and H. J. Mattausch, “Fully Parallel Nearest Manhattan-distance Search Memory with Large Reference-pattern Number,” Extend. Abst. Of the Int. Conf. on Solid State Devices and Materials (SSDM′ 2002), pp. 254-255, 2002.
[Non-Patent Document 5] M. A. Abedin, Y. Tanaka, A. Ahmadi, T. Koide and H. J. Mattausch, “Mixed Digital-Analog Associative Memory Enabling Fully-Parallel Nearest Euclidean Distance Search,” Japanese Journal of Applied Physics (JJAP), vol. 46, NO. 4B, in press, (accepted on Jan. 12, 2007).